package com.mashibing.class17;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

//打印一个字符串的全部子序列
public class Code03_PrintAllSubsquences {
    // s -> "abc" ->
    public static List<String> subs(String s) {
        System.out.println("subs s = " + s);
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<String>();
        process1(str, 0, ans, path);
        return ans;
    }

    // str 固定参数
    // 来到了str[index]字符，index是位置
    // str[0..index-1]已经走过了！之前的决定，都在path上
    // 之前的决定已经不能改变了，就是path
    // str[index....]还能决定，之前已经确定，而后面还能自由选择的话，
    // 把所有生成的子序列，放入到ans里去
    public static void process1(char[] str, int index, List<String> ans, String path) {
        if (index == str.length) { // index 到了结尾了, 说明是终止位置了.
            ans.add(path);
            return;
        }
        // 没有要index位置的字符
        process1(str, index + 1, ans, path);
        // 要了index位置的字符
        process1(str, index + 1, ans, path + String.valueOf(str[index]));
    }

    public static List<String> subsNoRepeat(String s) {
        char[] str = s.toCharArray();
        String path = "";
        HashSet<String> set = new HashSet<String>();
        process2(str, 0, set, path);
        List<String> ans = new ArrayList<String>();
        for (String cur : set) {
            ans.add(cur);
        }
        return ans;
    }

    public static void process2(char[] str, int index, HashSet<String> set, String path) {
        if (index == str.length) {
            set.add(path);
            return;
        }
        String no = path;
        process2(str, index + 1, set, no);
        String yes = path + String.valueOf(str[index]);
        process2(str, index + 1, set, yes);
    }

    public static void main(String[] args) {
        String test = "acccc";
        List<String> ans1 = subs(test);
//        List<String> ans2 = subsNoRepeat(test);
        System.out.println("ans1.size() = " + ans1.size());
//        for (String str : ans1) {
//            System.out.println(str);
//        }
        System.out.println("=================");
//        for (String str : ans2) {
//            System.out.println(str);
//        }
//        System.out.println("=================");

    }
}
